package com.xinwei.leetcode.数组;

import java.util.ArrayList;
import java.util.List;

//  https://leetcode-cn.com/problems/pascals-triangle/
public class _118_杨辉三角 {
    public static List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> lists = new ArrayList<>(numRows);
        ArrayList<Integer> first = new ArrayList<>(1);
        first.add(1);
        lists.add(first);
        if (numRows == 1) return lists;
        ArrayList<Integer> second = new ArrayList<>(2);
        second.add(1);
        second.add(1);
        lists.add(second);
        if (numRows == 2) return lists;
        for (int i = 2; i < numRows; i++) {
            ArrayList<Integer> childList = new ArrayList<>(i + 1);
            childList.add(1);
            for (int j = 1; j < i; j++) {
                childList.add(j, lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
            }
            childList.add(1);
            lists.add(childList);
        }
        return lists;
    }
}
